package a12_SeqList.LoopQueue;

import a12_SeqList.LinkedQueue.Queue;

import java.util.NoSuchElementException;

/**
 * @Author quan
 * @Description 循环队列：底层用数组实现
 * @Date 2023/3/23 11:15
 */
public class LoopQueue<E> implements Queue<E> {
    //用数组实现循环队列:因为数组是定长的
    private Object[] data;
    //队列中的实际有效长度
    private int size;
    //队列的头
    private int head;
    //队列的尾
    private int tail;
    //循环队列的创建大小比数组长度多创建一个空间
    public LoopQueue(){
        this(10);
    }
    public LoopQueue(int size) {
        this.data = new Object[size+1];
    }
    /**
     * 入队列
     */
    @Override
    public void offer(E element) {
        //判断队列是否已满，已满则抛出异常
        if(isFull()){
            throw new IllegalStateException("queue is full!cannot offer");
        }
        //否则在尾部插入元素
        data[tail] = element;
        //更新tail的值
        tail = (tail+1)%data.length;
        size++;
    }
    /**
     * 判断队列是否已满
     */
    private boolean isFull() {
        return head==(tail+1)%data.length;
    }

    /**
     * 出队列
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot poll");
        }
        E val= (E)data[(head)];
        head = (head+1)% data.length;
        size--;
        return val;
    }
    /**
     * 获取队首的元素值
     */
    @Override
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot peek!");
        }
        return (E) data[head];
    }
    /**
     * 判断当前队列是否为空
     */
    private boolean isEmpty() {
        return (head==tail);
    }

    /**
     * 重写toString方法
     */
    @Override
    public String toString() {
        //---------重点：最后一个有效元素的索引是多少？--------
        int lastIndex = (tail == 0? data.length-1:tail-1);
        //取最后一个值的索引：根据tail情况判断：如果tail==0,则最后一个索引位置为数组长度-1；如果tail！=0，则最后一个元素的位置就是tail-1
        StringBuilder sb = new StringBuilder();
        sb.append("[front");
        for (int i = head; i != tail;i = (i+1)%data.length) {
            sb.append(data[i]);
            if(i!=lastIndex){
                sb.append(", ");
            }
        }
        sb.append("]tail");
        return sb.toString();
    }
}
